package com.hanxiaozhang.greedy;

import java.util.HashSet;

/**
 * 〈一句话功能简述〉<br>
 * 〈居民点放等问题〉
 *
 * @author hanxinghua
 * @create 2021/9/23
 * @since 1.0.0
 */
public class Light {


    /**
     * 给定一个字符串str，只由 "X" 和 "." 两种字符构成。
     * "X" 表示墙，不能放灯，也不需要点亮。
     * "." 表示居民点，可以放灯，需要点亮。
     * 如果灯放在 i 位置，可以让 i-1 ，i 和 i+1 三个位置被点亮，
     * 返回如果点亮str中所有需要点亮的位置，至少需要几盏灯。
     *
     * @param args
     */
    public static void main(String[] args) {
        int len = 20;
        int testTime = 100;
        for (int i = 0; i < testTime; i++) {
            String test = randomString(len);
            System.out.println("str is " + test);
            int ans1 = minLight1(test);
            int ans2 = minLight2(test);
            if (ans1 != ans2) {
                System.out.println("oops!");
            }
        }
        System.out.println("finish!");
    }


    /**
     * 暴力递归
     *
     * @param road
     * @return
     */
    public static int minLight1(String road) {
        if (road == null || road.length() == 0) {
            return 0;
        }
        return process(road.toCharArray(), 0, new HashSet<>());
    }

    /**
     * 具体过程：
     * str[index ...]位置，自由选择是否放灯，
     * str[0,index]位置，已经做完决定，那些位置放了灯，存在lights里
     * 要求选出，能照亮所有"."方案，并在这些有效的方案中，返回最少需要的。
     *
     * @param str
     * @param index
     * @param lights
     * @return
     */
    private static int process(char[] str, int index, HashSet<Integer> lights) {
        // index来到str.length，即结束的时候
        // 结束的时候，验证是否所有"."是否被照亮
        if (index == str.length) {
            for (int i = 0; i < str.length; i++) {
                // 当前位置是点，
                if (str[i] == '.') {
                    // 查询，i-1位置、i位置、i+1位置是否有灯。如果都没有返回Integer.MAX_VALUE
                    if (!lights.contains(i - 1)
                            && !lights.contains(i)
                            && !lights.contains(i + 1)) {
                        return Integer.MAX_VALUE;
                    }
                }
            }
            // 返回用几盏灯
            return lights.size();
        } else {
            // 当前index位置没有放灯，直接去index+1的情况
            int no = process(str, index + 1, lights);
            int yes = Integer.MAX_VALUE;
            // 当前index是点，可以选择放灯
            if (str[index] == '.') {
                // 放灯，去遍历
                lights.add(index);
                yes = process(str, index + 1, lights);
                // 遍历完删除掉，恢复现场
                lights.remove(index);
            }
            return Math.min(no, yes);
        }
    }

    /**
     * 分析：
     * <p>
     * i位置是X 不需要放灯
     * <p>
     * i位置是.
     * 1) i+1是x 放灯，在i+2继续做决策
     * 2) i+1 是.
     * 2.1) i+2 是x  在i+1 放灯，在i+3继续做决策
     * 2.2) i+2 是.  在i+1 放灯，在i+3继续做决策
     *
     * @param road
     * @return
     */
    public static int minLight2(String road) {
        char[] str = road.toCharArray();
        int index = 0;
        int light = 0;
        while (index < str.length) {
            // index 是 x
            if (str[index] == 'X') {
                index++;
                // index 是 .
            } else {
                // 一定放灯
                light++;
                // index+1等于数组长度，结束循环
                if (index + 1 == str.length) {
                    break;
                } else {
                    // index+1是x，index+2赋值给index
                    if (str[index + 1] == 'X') {
                        index = index + 2;
                        // index+1是.，index+3赋值给index
                    } else {
                        index = index + 3;
                    }
                }
            }
        }
        return light;
    }

    /**
     * 生成器
     *
     * @param len
     * @return
     */
    public static String randomString(int len) {
        char[] res = new char[(int) (Math.random() * len) + 1];
        for (int i = 0; i < res.length; i++) {
            res[i] = Math.random() < 0.5 ? 'X' : '.';
        }
        return String.valueOf(res);
    }

}
